package algorithm.greedy;

import java.util.*;

/**
 * 贪心算法 解决 集合覆盖问题
 *
 * @author jack.wu
 * @version 1.0
 * @date 2020-04-06
 */
public class GreedyAlgorithm {

    public static void main(String[] args) {

        // 创建广播map
        Map<String, Set<String>> broadcasts = new HashMap<>(8);

        // 创建广播对应覆盖的地区
        Set<String> k1 = new HashSet<>(8);
        k1.add("北京");
        k1.add("上海");
        k1.add("天津");
        Set<String> k2 = new HashSet<>(8);
        k2.add("广州");
        k2.add("北京");
        k2.add("深圳");
        Set<String> k3 = new HashSet<>(8);
        k3.add("成都");
        k3.add("上海");
        k3.add("杭州");
        Set<String> k4 = new HashSet<>(8);
        k4.add("上海");
        k4.add("天津");
        Set<String> k5 = new HashSet<>(8);
        k5.add("杭州");
        k5.add("大连");

        // 加入到map
        broadcasts.put("k1", k1);
        broadcasts.put("k2", k2);
        broadcasts.put("k3", k3);
        broadcasts.put("k4", k4);
        broadcasts.put("k5", k5);

        // 存放所有地区
        Set<String> allArea = new HashSet<>(10);
        allArea.addAll(k1);
        allArea.addAll(k2);
        allArea.addAll(k3);
        allArea.addAll(k4);
        allArea.addAll(k5);

        // 创建存放选择的广播集合
        List<String> selects = new ArrayList<>(10);

        Set<String> tempSet = new HashSet<>(10);

        // 保存在一次遍历过程中 能够覆盖最大未覆盖地区对应广播key
        String maxKey ;
        while (allArea.size() != 0) {
            maxKey = null;
            for (String key : broadcasts.keySet()) {
                // 注意 每次都要clear
                tempSet.clear();
                // 当前广播覆盖的地区
                Set<String> areas = broadcasts.get(key);
                tempSet.addAll(areas);
                // 当前广播覆盖的地区和所有地区取交集
                tempSet.retainAll(allArea);
                // 体现贪心算法 每次选择最优
                if (tempSet.size() > 0 && (maxKey == null || tempSet.size() > broadcasts.get(maxKey).size())) {
                    maxKey = key;
                }
            }
            // 如果找到 还有最大未覆盖地区对应的广播
            if (maxKey != null) {
                selects.add(maxKey);
                // 在所有区域列表中移除选择的
                allArea.removeAll(broadcasts.get(maxKey));
            }
        }
        System.out.println("得到的最优选择：" + selects);

    }


}
